package com.janushuang.algorithm.sorter;

import java.lang.reflect.Array;

/**
 * @author zhijing.huang
 *         Created by zhijing.huang on 2014/9/26.
 */
public class MergeSorter<E extends Comparable<E>> extends Sorter<E> {
    @Override
    public void sort(E[] data, int from, int len) {
        if (len<=1) return;
        E[] temp = (E[]) Array.newInstance(data[0].getClass(),len);
        mergeSort(data,from,from+len-1,temp);
    }

    private final void mergeSort(E[] data, int from, int to, E[] temp) {
        if (to <= from) {
            return;
        }

        int middle = (from+to)/2;
        mergeSort(data,from,middle,temp);
        mergeSort(data,middle+1,to,temp);
        merge(data,from,to,middle,temp);
    }

    private final void merge(E[] data, int from, int to, int middle, E[] temp) {
        int k=0, leftIndex = 0, rightIndex=to-from;
        System.arraycopy(data,from,temp,0,middle-from+1);
        for (int i=0;i<to-middle;i++) {
            temp[to-from-i]=data[middle+i+1];
        }
        while (k<to-from+1) {
            if(temp[leftIndex].compareTo(temp[rightIndex])<0) {
                data[k+from]=temp[leftIndex++];
            } else {
                data[k+from] = temp[rightIndex--];
            }
            k++;
        }

    }
//    @Override
//    public void sort(int[] data) {
//        int[] temp=new int[data.length];
//        mergeSort(data,temp,0,data.length-1);
//    }
//
//    private void mergeSort(int[] data,int[] temp,int l,int r){
//        int mid=(l+r)/2;
//        if(l==r) return ;
//        mergeSort(data,temp,l,mid);
//        mergeSort(data,temp,mid+1,r);
//        for(int i=l;i<=r;i++){
//            temp[i]=data[i];
//        }
//        int i1=l;
//        int i2=mid+1;
//        for(int cur=l;cur<=r;cur++){
//            if(i1==mid+1)
//                data[cur]=temp[i2++];
//            else if(i2>r)
//                data[cur]=temp[i1++];
//            else if(temp[i1]<temp[i2])
//                data[cur]=temp[i1++];
//            else
//                data[cur]=temp[i2++];
//        }
//    }
}
